package com.lz.utils;

import com.lz.linklist.LinkList;
import com.lz.linklist.Node;
import lz.firstinterview.BinaryTree;

public class LinkListToTree<T> {
    /**
     * 找到链表的中间节点
     * @param head
     * @return
     */
    public Node<T> findMidle(Node<T> head) {
        Node<T> slow = head;
        Node<T> fast = head;
        Node<T> prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //断开链表
        //Node<T> mid = slow.next;
        if(prev != null) {
            prev.next = null;
        }

        return slow;
    }

    /**
     * 构建搜索二叉树
     * @param head
     * @return
     */
    public lz.firstinterview.Node<T> buildTree(Node<T> head) {
        if(head == null) {
            return null;
        }
        Node<T> mid = findMidle(head);

        lz.firstinterview.Node<T> treeNode = new lz.firstinterview.Node<T>();
        treeNode.setData(mid.getData());

        if(head == mid) {
            return treeNode;
        }

        treeNode.setLeft(buildTree(head));
        treeNode.setRight(buildTree(mid.next));
        return treeNode;

    }

    /**
     * 搜索二叉树插入节点
     * @param root, node
     * @return
     */
    public lz.firstinterview.Node<String> insertBuildTree(lz.firstinterview.Node<String> root, lz.firstinterview.Node<String> node) {
        if(root == null) {
            return node;
        }
        if(Integer.parseInt(root.getData()) > Integer.parseInt(node.getData())) {
            lz.firstinterview.Node<String> left = insertBuildTree(root.getLeft(), node);
            if(root.getLeft() == null ) {
                root.setLeft(left);
            }
        } else {
            lz.firstinterview.Node<String> right = insertBuildTree(root.getRight(), node);
            if(root.getRight() == null ) {
                root.setRight(right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        LinkListToTree<String> linkListToTree = new LinkListToTree<>();
        LinkList<String> linkList = new LinkList<>();
//        linkList.add("1");
//        linkList.add("4");
//        linkList.add("9");
//        linkList.add("5");
//        linkList.add("8");
//        linkList.add("6");
//        linkList.add("7");
//        linkList.add("2");

        linkList.add("1");
        linkList.add("2");
        linkList.add("3");
        linkList.add("4");
        linkList.add("5");
        linkList.add("6");
        linkList.add("7");
        linkList.add("8");
        linkList.add("9");

        linkList.printAll();

        lz.firstinterview.Node<String> treeNode = linkListToTree.buildTree(linkList.getHead());
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.traversePreorder(treeNode, 0);
        lz.firstinterview.Node<String> node = new lz.firstinterview.Node<String>();
        node.setData("10");
        linkListToTree.insertBuildTree(treeNode, node);
        node = new lz.firstinterview.Node<String>();
        node.setData("11");
        linkListToTree.insertBuildTree(treeNode, node);
        node = new lz.firstinterview.Node<String>();
        node.setData("12");
        linkListToTree.insertBuildTree(treeNode, node);
        System.out.println();
        binaryTree.traversePreorder(treeNode, 0);
    }
}
